/*
 * @lc app=leetcode.cn id=35 lang=cpp
 *
 * [35] 搜索插入位置
 *
 * 方法1：二分搜索
 */

#include <vector>
#include <iostream>

// @lc code=start
class Solution
{
public:
    int searchInsert(std::vector<int> &nums, int target)
    {
        const int len = nums.size();
        int low = 0, high = len - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                low = mid + 1;
            else
                high = mid - 1;
        }

        nums.insert(nums.begin() + low, target);
        return low;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> nums = {1, 3, 5, 6};
    std::cout << solution.searchInsert(nums, 7) << std::endl;
    for (auto n : nums)
        std::cout << n << " ";
    std::cout << std::endl;

    return 0;
}